Today, a large number of computer systems employ cache memories. A cache is a very fast, local storage memory that is used by the processor. Caches typically comprise fast, expensive static random access memories (SRAMs). In a data flow of a computer system, a cache is located between the microprocessor and the main system memory and holds copies of code and data that are frequently requested from the main system memory by the microprocessor, thereby improving the average memory response time.
A cache has three basic components: a data cache RAM, a tag RAM and cache management logic. The data cache RAM is the block of fast memory that stores copies of data or instructions frequently requested by the microprocessor. The tag RAM holds the main system memory addresses of the code and data stored in the data cache RAM plus additional status bits used by the cache management logic. Each entry in the tag RAM is called a "tag". The cache management logic compares the memory requests of the microprocessor, which are in the form of memory addresses, to the stored address in the tag RAM. When the memory request address matches an address stored in the tag RAM, the cache returns the information from the data cache RAM. This action is commonly referred to as a cache hit. If the memory request address does not match any entry in the tag RAM directory, the memory request is passed to the main memory of the computer system. This action is commonly referred to as a cache miss. When the information requested is returned from the main system memory to the processor, a copy may be stored in the cache for future use.
Caches are currently designed at one of a number of levels (e.g., first level caches, second level caches, etc.). A first level cache is a single layer of high speed memory between the microprocessor and the main system memory (typically, dynamic RAM (DRAM) memory) which stores copies of code and data most frequently requested by the microprocessor. Furthermore, first level caches are often on the same integrated circuit of the microprocessor and are typically small in size (e.g., 4 kilobytes (KB) to 64 KB). A second level cache is a second layer of high speed memory between the first level cache and the main system DRAM memory. The second level cache also holds copies of code and data frequently requested by the microprocessor. However, the second level cache is almost always larger than the first level cache (e.g., 64 KB to 512 KB), such that the second level cache is able to hold all of the data and code in the first level cache and more to compensate for first level cache misses. Note that while control for a first level cache is often on-chip with the cache, the control for a second level cache is often handled by a cache controller.
One primary concern with the use of caches involves multiprocessing systems. A cache consistency problem may arise from the fact that data from a given memory location may reside simultaneously in main memory and in one or more cache memories. Furthermore, the data in one cache may have a value different from that in memory, because one has been updated more recently. Such inconsistencies can arise in single processor systems where there are other bus masters, such as direct memory access (DMA) or intelligent device drivers besides the central processing unit (CPU), which can access the main memory. It is desirable to have a method and mechanism to ensure that all references to a main-memory location retrieve the most recent value of the data.
In multiprocessing systems where multiple processes can act on data and code, many caches implement a "write back" design with support for multiprocessing data consistency. A write-back cache memory may have data which is not updated in the main memory. Therefore, a mechanism is implemented to insure that the data read by any system bus master at any time is correct. That is, when a particular memory location in main memory is to be read, if the data is in a cache and has been modified, the data is written back to main memory before the data is returned for the read. In this manner, bus masters are always assured of obtaining the most up-to-date data.
The operation of writing data from the cache back into main memory is known as flushing the cache. There are two types of flushing. One type of flushing involves writing the data back to main memory because another processor desires the data. The other type of flushing occurs where a section (or all) of a cache is to be flushed or invalidated. This may occur to avoid the situation where data is desired by another processor. It is desirable to be able to cause the cache to be flushed (or invalidated) at times other than those specified by the write back algorithm.
Note that flushing a second level cache is usually performed by external logic, such as the cache controller. Furthermore, each flushing operation performed on the cache usually occurs one line at a time. The time required to specify each line individually adds to the overall operation time where multiple lines must be flushed. When data is written back to main memory, the use of the system bus takes longer because it is a slower bus. It would be desirable to take advantage of the faster local bus to write back the data in the cache. It would also be desirable to flush the cache without relying on the use of external mechanisms, such as a cache controller. Also it is desirable to flush more than one line of the cache at a time.
In multiprocessing systems, for another processor to cause data to be written back from the cache of another processor, a memory cycle must be initiated on the slow system bus. A snoop detector must recognize the address on the system bus as being in the cache, such that the memory bus cycle can be stalled to allow for the most recent copy of the data to be written back to the main memory. Therefore, in a multiprocessing environment, large amounts of time are consumed before data is even written back into the cache. It is desirable to have a processor in a multiprocessing system to be able to cause another processor to have the data in a cache written back to main memory.
In the prior art, software and hardware is used to maintain cache consistency between data stored in the main memory of the system and the cache memories. One cache consistency protocol known as the M.E.S.I. protocol (i.e., Modified, Exclusive, Shared and Invalid) is implemented in hardware. The MESI model is implemented by assigning state bits for each cache line. The MESI represents four states which define whether a line is valid (hit or miss), if it is available in other caches (shared or exclusive), and if it is modified (has been modified). These states are dependent on both the cache controller data transfer activities performed as a bus master and snooping activities performed in response to snoop requests generated by other memory bus masters.
Note that when using cache consistency protocols, such as MESI, upon powering up a computer system, data in the cache may be marked as valid. A reset routine normally performs a cache invalidation operation when a computer system is powered up, wherein each cache line is accessed and marked invalid one line at a time. Furthermore, this invalidation process occurs over the slow system bus. It is desirable to be able to invalidate more than one line at a time upon reset and to have such an invalidation process performed on a faster bus, such as the local bus. Moreover, it is also desirable to be able to alter the MESI state, other than by flushing the cache.
The present invention provides a method and means for having a processor control an external cache, such that no external logic is required. Furthermore, the present invention provides a mechanism to write back multiple lines of a cache in one operation and at times other than those specified by the normal writeback algorithm. The present invention also includes a method and apparatus for altering the MESI state of cache lines within the cache.